package com.gjh.study.algorithm4.sort;

import edu.princeton.cs.algs4.StdOut;

public class MergeBU extends SortBase {
    // 辅助数组
    private static Comparable[] aux;

    @Override
    public void sort(Comparable[] a) {
        // 进行 logN 次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            StdOut.println("sz=" + sz);
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                // hi 的取值，根据数组大小来判断，最后一组子数组的大小可能不一致，则取整个数组的 hi 值，计算 mid
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
                show(a);
            }
        }
    }

    /**
     * 这里的 a[] ，左右两边已经是排好序的子数组
     **/
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        StdOut.println("merge(a, " + lo + ", " + mid + ", " + hi + ")");
        int i = lo, j = mid + 1;
        // a 复制到 aux
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        // 归并回到 a
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                // 左边已经全部归并完成了，直接把右边剩余的依次归并到 a[] 对应位置
                a[k] = aux[j++];
            } else if (j > hi) {
                // 右边全部归并完成了，直接把左边剩余的依次归并 a[] 对应位置
                a[k] = aux[i++];
            }
            // 左右两边相应位置逐个进行比较，把较小的归并到 a[] 相应位置
            else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
}
